// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-24 23:14
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.ArraysTrain.preFixTrain;

import org.junit.jupiter.api.Test;

public class ChalkReplacer {
    /**
     * 找出需要补充粉笔的学生
     * 使用前缀和的时候，当数组长度很长，而且数据元素很大的时候，容易导致数据元素溢出
     */
    public int chalkReplacer(int[] chalk, int k) {
        if (chalk[0] > k) {
            return 0;
        }

        /*-----构造前缀和数组-----*/
        int[] preFix = new int[chalk.length];
        preFix[0] = chalk[0];
        for (int i = 1; i < chalk.length; i++) {
            preFix[i] += preFix[i - 1] + chalk[i];
            if (preFix[i] > k) {
                return i;
            }
        }
        // 获取最后一次遍历的状态
        k %= preFix[chalk.length - 1];
        for (int i = 0; i < chalk.length - 1; i++) {
            if (preFix[i] > k) {
                return i;
            }
        }
        return chalk.length - 1;
    }


    @Test
    public void shout() {
        int[] test = {3, 4, 1, 2};
        int cnt = 25;
        System.out.println(chalkReplacer(test, cnt));

    }
}
